{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #跳跃训练"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #memoization #math #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #记忆化搜索 #数学 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: trainWays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #跳跃训练"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>今天的有氧运动训练内容是在一个长条形的平台上跳跃。平台有 <code>num</code> 个小格子，每次可以选择跳 <strong>一个格子</strong> 或者 <strong>两个格子</strong>。请返回在训练过程中，学员们共有多少种不同的跳跃方式。</p>\n",
    "\n",
    "<p>结果可能过大，因此结果需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 5\n",
    "<strong>输出：</strong>8\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= n &lt;= 100</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>注意：本题与主站 70 题相同：<a href=\"https://leetcode-cn.com/problems/climbing-stairs/\">https://leetcode-cn.com/problems/climbing-stairs/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [qing-wa-tiao-tai-jie-wen-ti-lcof](https://leetcode.cn/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [qing-wa-tiao-tai-jie-wen-ti-lcof](https://leetcode.cn/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2', '5']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def trainWays(self, n: int) -> int:\n",
    "#         if n == 0 or n ==1: return 1\n",
    "#         elif n == 2: return 2\n",
    "#         else:\n",
    "#             dp = []\n",
    "#             dp.append(1)\n",
    "#             dp.append(2)\n",
    "#             for i in range(2, n):\n",
    "#                 dp_tmp = (dp[i - 2] + dp[i - 1]) % 1000000007\n",
    "#                 dp.append(dp_tmp)\n",
    "#             return dp[n - 1] #直接从1阶开始算，n阶对应列表中的第n-1个值\n",
    "\n",
    "#方法二\n",
    "class Solution:\n",
    "    def trainWays(self, n: int) -> int:\n",
    "        a = 1\n",
    "        b = 1\n",
    "        for _ in range(n):\n",
    "            a, b = b, a + b\n",
    "        return a % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        a, b = 1, 1\n",
    "        for i in range(num):\n",
    "            a, b = b, (a+b) % (1000000007)\n",
    "        return a\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        dp = [1, 1]\n",
    "        for _ in range(num - 1):\n",
    "            dp = [dp[1], (dp[0] + dp[1]) % (10 ** 9 + 7)]\n",
    "        return dp[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        # 1 1 2 3 5 8\n",
    "        # 0 1 2 3 4 5\n",
    "        ans = [1, 1, 2]\n",
    "        for i in range(3, num+1):\n",
    "            ans.append(ans[i-1] + ans[i-2])\n",
    "        return ans[num] % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        a, b = 1, 1\n",
    "        for _ in range(num):\n",
    "            a, b = b, a + b\n",
    "        return a % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        dp = [1 for i in range(num+1)]\n",
    "        for i in range(2, num+1):\n",
    "            dp[i] = dp[i-1]+dp[i-2]\n",
    "        return dp[num] % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        if num == 0 or num == 1:\n",
    "            return 1\n",
    "        if num == 2:\n",
    "            return num\n",
    "        a, b = 1, 2\n",
    "        for _ in range(3, num + 1):\n",
    "            a, b = b, (a + b) % 1000000007\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        if num == 0 or num == 1:\n",
    "            return 1\n",
    "        \n",
    "        dp = [0] * (num + 1)\n",
    "        dp[0], dp[1] = 1, 1\n",
    "\n",
    "        for i in range(2, num + 1):\n",
    "            dp[i] = dp[i - 1] + dp[i - 2]\n",
    "        \n",
    "        return dp[num] % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        if num == 0:\n",
    "            return 1\n",
    "        dp = [0] * (num + 1)\n",
    "        dp[0] = 1\n",
    "        dp[1] = 1\n",
    "        for k in range(2, num+1):\n",
    "            dp[k] = dp[k-1] + dp[k-2]\n",
    "\n",
    "        return dp[num] % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        if num == 0:\n",
    "            return 1\n",
    "        \n",
    "        if num == 1:\n",
    "            return 1\n",
    "\n",
    "        dp = [0 for _ in range(num + 1)]\n",
    "\n",
    "        dp[1] = 1\n",
    "        dp[2] = 2\n",
    "\n",
    "        for i in range(3, num+1):\n",
    "            dp[i] = dp[i-1] + dp[i-2]\n",
    "        \n",
    "        return dp[num] % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        a, b = 1, 1\n",
    "        for _ in range(num):\n",
    "            a, b = b, a + b\n",
    "        return a % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        \n",
    "        if num == 0:\n",
    "            return 1\n",
    "        a, b = 1, 2\n",
    "        for _ in range(num-1):\n",
    "            a, b = b, (a+b)%1000000007\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        if num in [0,1]:\n",
    "            return 1\n",
    "        if num == 2:\n",
    "            return 2\n",
    "        \n",
    "        a = 1\n",
    "        b = 2\n",
    "        ans = 0\n",
    "        #第N次跳法f(n)=f(n-1)+f(n-2),递推法\n",
    "        for i in range(3,num+1):\n",
    "            ans = (a + b)%1000000007\n",
    "            a = b\n",
    "            b = ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        a, b = 0, 1\n",
    "        for _ in range(num):\n",
    "            a, b = b, a + b\n",
    "        return b % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        if num == 0:\n",
    "            return 1\n",
    "        elif num == 1:\n",
    "            return 1\n",
    "        elif num == 2:\n",
    "            return 2\n",
    "        mode = 1e9 + 7\n",
    "        dp = [0] * num\n",
    "        dp[0] = 1\n",
    "        dp[1] = 2\n",
    "        for i in range(2,num):\n",
    "            dp[i] = (dp[i-1] + dp[i-2])%mode\n",
    "        return int(dp[-1] )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        if num == 1:\n",
    "            return 1\n",
    "        a, b = 1, 2\n",
    "        #1, 2\n",
    "        #2, 3\n",
    "        #3, 5\n",
    "        for i in range(num-1):\n",
    "            a, b = b, (a+b)%1000000007\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        if num==0 or num==1:\n",
    "            return 1\n",
    "       \n",
    "        pre =2\n",
    "        prepre=1\n",
    "        for i in range(3,num+1):\n",
    "            prepre,pre=pre,pre+prepre\n",
    "        return pre%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 不考虑大数越界问题\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        a, b = 1, 1\n",
    "        for _ in range(num):\n",
    "            a, b = b, a + b\n",
    "        return a % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        # if num == 0 : return 1\n",
    "        a , b = 1, 1\n",
    "        for _ in range(num):\n",
    "            a, b = b ,(a+b)%(10**9+7)\n",
    "        return a\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        a = 1\n",
    "        b = 2\n",
    "        for i in range(1, num):\n",
    "            a,b = b, (a+b)\n",
    "        return a % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        a, b = 1, 1\n",
    "        for _ in range(num):\n",
    "            a, b = b, (a + b) % 1000000007\n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        if num < 2:\n",
    "            return 1\n",
    "        dp = [0] * (num + 1)\n",
    "        dp[0] = 1\n",
    "        dp[1] = 1\n",
    "        for i in range(2, num + 1):\n",
    "            dp[i] = (dp[i - 1] + dp[i - 2]) % (10 ** 9 + 7)\n",
    "        return dp[num]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        a, b = 1, 1\n",
    "        for _ in range(num):\n",
    "            a, b = b, a + b\n",
    "        return a % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        a, b = 1, 1\n",
    "        for _ in range(num):\n",
    "            a, b = b, (a + b) % 1000000007\n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    MOD = 1e9 + 7\n",
    "    def trainWays(self, n: int) -> int:\n",
    "        self.memo = [-1] * (n + 1)\n",
    "        return self.dp(n)\n",
    "\n",
    "    # 定义：爬到第 n 级台阶的方法个数为 dp(n)\n",
    "    def dp(self, n: int) -> int:\n",
    "        # base case\n",
    "        if n <= 2:\n",
    "            return n if n else 1\n",
    "\n",
    "        if self.memo[n] != -1:\n",
    "            return self.memo[n]\n",
    "\n",
    "        # 状态转移方程：\n",
    "        # 爬到第 n 级台阶的方法个数等于爬到 n - 1 的方法个数和爬到 n - 2 的方法个数之和。\n",
    "        self.memo[n] = self.dp(n - 1) + self.dp(n - 2)\n",
    "        return round(self.memo[n] % self.MOD)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        #dp[i]:跳到第i个台阶有dp[i]种方法\n",
    "        if num==0:\n",
    "            return 1\n",
    "        if num==1:\n",
    "            return 1\n",
    "      \n",
    "\n",
    "        dp=[0 for _ in range(num+1)]\n",
    "        dp[0]=1\n",
    "        dp[1]=1\n",
    "      \n",
    "        for i in range(2,num+1):\n",
    "            dp[i]=dp[i-1]+dp[i-2]\n",
    "           \n",
    "        return dp[-1]%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        if num == 0:\n",
    "            return 1\n",
    "        if num == 1:\n",
    "            return 1\n",
    "        if num == 2:\n",
    "            return 2\n",
    "        a, b = 1, 2\n",
    "        for i in range(2, num):\n",
    "            result = a + b\n",
    "            a = b\n",
    "            b = result\n",
    "        return result % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        if num<2:\n",
    "            return 1\n",
    "        p, q, r = 0, 0, 1\n",
    "        for i in range(2, num+2):\n",
    "            p = q\n",
    "            q = r\n",
    "            r = p+q\n",
    "        return r%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        if num<2:\n",
    "            return 1\n",
    "        dp = [0]*(num+1)\n",
    "        dp[0] = 1\n",
    "        dp[1] = 1\n",
    "        for i in range(2, num+1):\n",
    "            dp[i] = int((dp[i-1]+dp[i-2])%(1e9+7))\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        fx1,fx2,fc = 1,2,0\n",
    "        for i in range(2,num+1):\n",
    "            fc = fx1 + fx2\n",
    "            fx1,fx2 = fx2,fc\n",
    "        return fx1 % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        if num == 1:return 1\n",
    "        a,b = 1,2\n",
    "        for i in range(num-1):\n",
    "            a,b = b,a+b\n",
    "        return a%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        if num == 0:\n",
    "            return 1\n",
    "        dp = [1,2]\n",
    "        for i in range(2,num):\n",
    "            number = (dp[i-1] +dp[i-2]) % 1000000007\n",
    "            dp.append(number)\n",
    "        return dp[num-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, n: int) -> int:\n",
    "        Mod = 1000000007\n",
    "        \n",
    "        dp = [1]*(n+1)\n",
    "        for i in range(2,n+1):\n",
    "            dp[i] = dp[i-1]+dp[i-2]\n",
    "        return dp[n]%Mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        a, b = 1, 1\n",
    "        for _ in range(num):\n",
    "            a, b = b, (a + b) % 1000000007\n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        a = b = 1\n",
    "        for _ in range(num):\n",
    "            a, b = b, a + b\n",
    "        return a % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        if num == 0:\n",
    "            return 1\n",
    "        if num <= 2:\n",
    "            return num\n",
    "        dp = [0] * (num + 1)\n",
    "        dp[1] = 1\n",
    "        dp[2] = 2\n",
    "        for i in range(3, num + 1):\n",
    "            dp[i] = dp[i - 1] + dp[i - 2]\n",
    "\n",
    "        return dp[-1] % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        a, b, mod = 1, 1, 10 ** 9 + 7\n",
    "        for _ in range(num):\n",
    "            a, b = b, (a+b) % mod\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, n: int) -> int:\n",
    "        if n<=1:\n",
    "            return 1\n",
    "        pre=cur=1\n",
    "        for i in range(2,n+1):\n",
    "            pre,cur=cur,pre+cur\n",
    "        return cur%(10**9+7)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        fx1,fx2,fc = 1,2,0\n",
    "        for i in range(2,num+1):\n",
    "            fc = fx1 + fx2\n",
    "            fx1,fx2 = fx2,fc\n",
    "        return fx1 % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        a, b = 0, 1\n",
    "        for i in range(num):\n",
    "            a, b = b, a+b\n",
    "        return b%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        a, b = 1, 1\n",
    "        for _ in range(num):\n",
    "            a, b = b, (a + b) % 1000000007\n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        if num ==0 or num==1:\n",
    "            return 1\n",
    "        dp = [0]*num\n",
    "        dp[0] = 1\n",
    "        dp[1] = 2\n",
    "        for i in range(2,num):\n",
    "            dp[i] = (dp[i-1]+dp[i-2])%(10**9+7)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        if num==0:return 1\n",
    "        if num==1:return 1\n",
    "        dp = [1,1]\n",
    "        next = dp[0] + dp[1]\n",
    "        for i in range(2,num):\n",
    "            dp[0] = dp[1]\n",
    "            dp[1] = int(next % (1e9 + 7))\n",
    "            next = int((dp[0] + dp[1]) %(1e9 + 7))\n",
    "        return next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        a, b = 1, 1\n",
    "        for _ in range(num):\n",
    "            a, b = b, (a + b) % 1000000007\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        if num==0:\n",
    "            return 1\n",
    "        i,j=0,1\n",
    "        for k in range(1,num+1):\n",
    "            i,j=j,i+j\n",
    "        return j%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        if num == 0: return 1\n",
    "        dp = [0] * (num+1)\n",
    "        dp[0] = 1\n",
    "        dp[1] = 2\n",
    "        for i in range(2, num+1):\n",
    "            dp[i] = dp[i-1] + dp[i-2]\n",
    "        return dp[num-1] % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        a, b = 1 , 1\n",
    "        for _ in range(num):\n",
    "            a, b = b , a+b\n",
    "        return a%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        a, b = 1, 1\n",
    "        for i in range(num):\n",
    "             a, b = b, a+b\n",
    "        return a % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        res = {}\n",
    "        res[0] = 1\n",
    "        res[1] = 1\n",
    "        res[2] = 2\n",
    "        for i in range(3, num+1):\n",
    "            res[i] = res[i-1] + res[i-2]\n",
    "        return res[num] % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        if num==0:\n",
    "            return 1\n",
    "        dp=[0]*(num+1)\n",
    "        dp[0]=1\n",
    "        dp[1]=1\n",
    "        for i in range(2,num+1):\n",
    "            dp[i]=dp[i-1]+dp[i-2]\n",
    "        #print(dp)\n",
    "        return dp[-1]%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        \n",
    "        f1, f2, f3 = 0, 0, 1\n",
    "        \n",
    "        for _ in range(num):\n",
    "            f1, f2, = f2, f3\n",
    "            f3 = (f1 + f2) % MOD\n",
    "        return f3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        a, b = 1, 1\n",
    "        for _ in range(num):\n",
    "            a, b = b, (a + b) % 1000000007\n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        a, b = 1, 1\n",
    "        for _ in range(num):\n",
    "            a, b = b, a + b\n",
    "        return a % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainWays(self, num: int) -> int:\n",
    "        if num == 0: return 1\n",
    "        series = [-1 for _ in range(num+1)]\n",
    "        for i in range(num+1):\n",
    "            if i == 0:\n",
    "                continue\n",
    "            if i == 1:\n",
    "                series[i] = 1\n",
    "                continue\n",
    "            if i == 2:\n",
    "                series[i] = 2\n",
    "                continue\n",
    "            series[i] = series[i-2] + series[i-1]\n",
    "        \n",
    "        return series[-1]% 1000000007"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
